/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 马拉圈
 * Date: 2023-06-20
 * Time: 3:13
 */
public class Main {
    public int maxProfit1(int[] prices) {
        int n = prices.length;
        int[] f = new int[n];
        int[] g = new int[n];
        int[] h = new int[n];
        f[0] = -prices[0];
        for(int i = 1; i < n; i++) {
            f[i] = Math.max(f[i - 1], g[i - 1] - prices[i]);
            g[i] = Math.max(g[i - 1], h[i - 1]);
            h[i] = f[i - 1] + prices[i];
        }
        return Math.max(
                Math.max(f[n - 1], g[n - 1]), h[n - 1]
        );
    }
    public int maxProfit2(int[] prices, int fee) {
        int n = prices.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = -prices[0];
        for(int i = 1; i < n; i++) {
            f[i] = Math.max(f[i - 1], g[i - 1] - prices[i]);
            g[i] = Math.max(g[i - 1], f[i - 1] + prices[i] - fee);
        }
        return Math.max(f[n - 1], g[n - 1]);
    }
    public int maxProfit3(int[] prices) {
        int n = prices.length;
        int[][] f = new int[n][3];
        int[][] g = new int[n][3];

        f[0][0] = -prices[0];
        for(int i = 1; i < 3; i++) {
            f[0][i] = -0x3f3f3f3f;
            g[0][i] = -0x3f3f3f3f;
        }
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < 3; j++) {
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if(j >= 1) {
                    g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }
        int min = -0x3f3f3f3f;
        for(int i = 0; i < 3; i++) {
            min = Math.max(min, f[n - 1][i]);
            min = Math.max(min, g[n - 1][i]);
        }
        return min;
    }
    public int maxProfit4(int k, int[] prices) {
        int n = prices.length;
        int[][] f = new int[n][k + 1];
        int[][] g = new int[n][k + 1];

        f[0][0] = -prices[0];
        for(int i = 1; i < k + 1; i++) {
            f[0][i] = -0x3f3f3f3f;
            g[0][i] = -0x3f3f3f3f;
        }
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < k + 1; j++) {
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if(j >= 1) {
                    g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }
        int min = -0x3f3f3f3f;
        for(int i = 0; i < k + 1; i++) {
            min = Math.max(min, f[n - 1][i]);
            min = Math.max(min, g[n - 1][i]);
        }
        return min;
    }
}
